The Infona portal uses cookies, i.e. strings of text saved by a browser on the user's device. The portal can access those files and use them to remember the user's data, such as their chosen settings (screen view, interface language, etc.), or their login data. By using the Infona portal the user accepts automatic saving and using this information for portal operation purposes. More information on the subject can be found in the Privacy Policy and Terms of Service. By closing this window the user confirms that they have read the information on cookie usage, and they accept the privacy policy and the way cookies are used by the portal. You can change the cookie settings in your browser.
The authors analyze two‐person zero‐sum search games of the following type. Play takes place on a network; the hider must choose a node and remain there while the searcher can choose the node at which he starts. To detect the hider, the searcher needs to conduct a search at the node chosen by the hider. Searching a node involves a cost which can vary from node to node. In addition to the search costs,...
The paper “Multistage Methods for Freight Train Classification” by Jacob et al. [Networks 57 (2011) 87–105] provides great insight into the theory and practice of sorting procedures at shunting yards. In Jacob et al. [Networks 57 (2011) 87–105] many relevant shunting situations (e.g., single or multiple inbound trains, single or multiple outbound trains, (un)restricted number of tracks, (un)restricted...
In many applications of multiple objective network programming (MONP) problems, only integer solutions are acceptable as the final optimal solution. Representative efficient solutions are usually obtained by sampling the efficient set through the solution of augmented weighted Tchebycheff network programs. Because such efficient solutions are usually not integer solutions, a branch‐and‐bound (BB)...
Relocation of service‐providers in response to changing real‐time needs is suboptimal due to limited foreknowledge of client requests. Simple cost schedules for relocation and remote‐service provision have been investigated both for the possibility of complete optimizability and the degree of inefficiency introduced by imperfect future knowledge. This work further explores a parametrization developed...
Motivated by the problem of link scheduling in wireless sensor networks where different sensors have different transmission and interference ranges and may be mobile, we study the problem of “distance edge coloring” of graphs, which is a generalization of proper edge coloring. Let Gbe a graph modeling a sensor network. An ℓ‐distance edge coloring of Gis a coloring of the edges of Gsuch that any two...
A multilayer network is a hierarchical network where each layer is built using the components of the previous one. Optical networks are an example of two layered networks. The multilayer network design problem consists of installing minimum cost integer capacities on the edges of all the layers so that a set of demands can be routed on the network. In this article, two versions of the optical network...
Previous studies of search in channel graphs have assumed global search, for which the status of any link can be probed by the search algorithm at any time. We consider for the first time local search, for which only links to which an idle path from the source has already been established may be probed. We show that some well‐known channel graphs may require exponentially more probes, on average,...
We consider a network design problem in which flow bifurcations are allowed. The demand data are assumed to be uncertain, and the uncertainties of demands are expressed by an uncertainty set. The goal is to install facilities on the edges at minimum cost. The solution should be able to deliver any of the demand requirements defined in the uncertainty set. We propose an exact solution algorithm based...
We consider a time‐dependent network with a continuous‐time variable, in which time constraints are imposed both on the arrival times and on the waiting times at the nodes. Under certain continuity assumptions, we prove the existence of optimal paths, and we show that the optimal value function is lower‐semicontinuous. We present an exact solution algorithm, which computes both the optimal value function...
In this article, we revisit a classical optimization problem occurring in designing survivable multicommodity flow networks. The problem, referred to as FR, assumes flow restoration that takes advantage of the so‐called stub release. As no compact linear programming (LP) formulation of FR is known and at the same time all known noncompact LP formulations of FR exhibit
\documentclass{article}\usepackage{mathrsfs}\usepackage{amsmath}\pagestyle{empty}\begin{document}\begin{align*}\mathcal{NP}\end{align*}...
We consider the following simple network design problem. The input consists of n weighted nodes, and the output is an edge‐weighted connected network such that the total weight of the edges incident to a node is at least the given weight of the node. We aim to design the cheapest connected network; that is, the reachability of the network should be guaranteed, and the network is better if its total...
We present an extension to nonatomic congestion games (NCG). An NCG models a large number of players depending on a set of resources (e.g., network links) in certain combinations (e.g., paths or multicast trees) called strategies. The rate of consumption ZeS specifies how aggressively resource e is consumed when used via strategy S, but it also effects how strongly the resource's latency is experienced...
We consider a transportation problem where the cost matrix satisfies the Monge property. The problem has supply nodes N1(|N1| = n1), demand nodes N2(|N2| = n2), supply si ≥ 0 for i∈N1, and demand dj ≥ 0 for j∈N2(n = n1 + n2,m = n1n2). When the total supply is equal to the total demand, the problem can be solved in O(n) time using the northwest corner rule (Hoffman [10]). This algorithm and run‐time,...
We consider the maximum flow problem with minimum quantities (MFPMQ), which is a variant of the maximum flow problem where the flow on each arc in the network is restricted to be either zero or above a given lower bound (a minimum quantity), which may depend on the arc. This problem has recently been shown to be weakly NP ‐complete even on series–parallel graphs. In this article, we provide further...
The k‐opt heuristics are among the most common techniques for approaching the traveling salesman problem (TSP). They are used either directly or as subroutines in more sophisticated heuristics, such as the celebrated Lin–Kernighan heuristic. The value of k is typically 2 or 3. In this article, we modify the 2‐opt heuristic to be based on a function f of the distances rather than the distances solely...
This article surveys the main contributions that have appeared in the scientific literature addressing resource constrained shortest path problems. The aim of this work is twofold: to give a structured survey of the literature on this topic; to provide a starting point for researchers who want to address the problems at hand. The study is focused on the relevant contributions dealing with exact solution...
We consider the problem of covering the edges of a graph by a sequence of matchings subject to the constraint that each edge e appears in at least a given fraction r(e) of the matchings. Although it can be determined in polynomial time whether such a sequence of matchings exists or not [Grötschel et al., Combinatorica (1981), 169–197], we show that several questions about the length of the sequence...
The ‐rainbow index of a graph G was introduced by Chartrand et al. (Network 54(2) (2009), 75–81; 55 (2010), 360–367). For the complete graph Kn of order , they showed that for . Furthermore, they conjectured that for every positive integer , there exists a positive integer N such that for every integer . More generally, they conjectured that for every...
Set the date range to filter the displayed results. You can set a starting date, ending date or both. You can enter the dates manually or choose them from the calendar.